#include"encode.h"
#include"constant.h"
#include"freq.h"
#include"list.h"
#include"utility.h"
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<values.h>

#define ENCODEMODE 0
#define DECODEMODE 1

void printFrequencyLatex(CharFreq * frequencies);
void buildCodeBookHelper(TreeNode * tn,int ** codebook,int * row,int col){

    if(NULL == tn){

        return;
    }
    //是否为叶节点
    TreeNode * lc = tn->left;
    TreeNode * rc = tn->right;
    // 叶子节点
    if(NULL == lc && rc == NULL){

        codebook[*row][0] = tn->value;
        (*row)++;
        return;
    }
    if(lc){

        // 填充子树整个列
        int numRow = Tree_leaf(lc);
        int index = 0;
        for(int index = (*row);index < (*row) + numRow;index++){

            codebook[index][col] = 0; 
        }
        // 编码下一列 col + 1
        buildCodeBookHelper(lc,codebook,row,col+1);
    }
    if(rc){

        int numRow = Tree_leaf(rc);
        int index = 0;
        for(int index = (*row);index < (*row) + numRow;index++){

            codebook[index][col] = 1;
        }
        // 编码下一列 col + 1
        buildCodeBookHelper(rc,codebook,row,col+1);
    }
}

void buildCodeBook(TreeNode * root,int ** codebook){

    int row = 0;
    buildCodeBookHelper(root,codebook,&row,1);
}

void printCodeBook(int * * codebook,int numRow){

    int row = 0;
    for(row = 0;row < numRow;row++)
    {

        printf("%c: ",codebook[row][0]);
        int col = 1;
        while (codebook[row][col]!=-1)
        {
            printf("%d ",codebook[row][col]);
            col++; 
        }
        printf("\n");
    }
}

int compress(char * infile,char * outfile,int ** codebook,int * mapping){

    FILE * infptr = fopen(infile,"r");
    if(NULL == infptr)
    {
        return 0;
    }
    FILE * outfptr = fopen(outfile,"a");
    if(NULL == outfptr){

        fclose(outfptr);
        return 0;
    }
    unsigned char whichbit = 0;
    unsigned char curbyte = 0;
    while(!feof(infptr))
    {
        int onechar = fgetc(infptr);
        if(onechar != EOF){

            // 这里的onechar映射的是对应在codebook的行（即mapping[onechar]的行）
            int index = mapping[onechar];
            int index2 = 1;
            // 
            while(codebook[index][index2] != -1){

                // 其实这里没有必要来进行比较 因为不是0就是1
                // 以byte的大小写入到文件
                writeBit(outfptr,codebook[index][index2] == 1,&whichbit,&curbyte);
                index2++;
            }
        }
    }
    // 填充0 需要根据whichbitd的值
    padZero(outfptr,&whichbit,&curbyte);
    fclose(infptr);
    fclose(outfptr);
    return 1;
}

// 如果encode为0: 编码，如果为1: 解码
// 编码和解码要按照数字的顺序翻转
// 子树
static ListNode * MergeListNode(ListNode * head,int endec){

    ListNode * second = head->next;
    ListNode * third = second->next;

    // second不能为空 third可以为空
    TreeNode * tn1 = head->tnptr;
    TreeNode * tn2 = second->tnptr;


    free(head);
    free(second);
    head = third;

    TreeNode * mrg;
    if(endec == ENCODEMODE){

        mrg = TreeNode_merge(tn1,tn2);
    }else{

        mrg = TreeNode_merge(tn2,tn1);
    }
    ListNode * ln = ListNode_create(mrg);
    if(endec == ENCODEMODE){
        
        head = List_insert(head,ln,SORTED);
    }else{
        // 这个模式下的链表是非排序的
        head = List_insert(head,ln,STACK);
    }
    return head;
}
// 
static TreeNode * list2Tree(ListNode * head){

    while(head->next!=NULL){

        head = MergeListNode(head,ENCODEMODE);
    }
    // List_print(head);
    TreeNode * root = head->next;
    free(head);
    return root;
}
// 做全局注释(编码函数)
int encode(char * infile,char * outfile){

    // 先定义全部的字符集0-127
    CharFreq * frequencies[NUMLETTER];
    // 置零
    bzero(frequencies,sizeof(CharFreq) * NUMLETTER);
    // 读取输入文件并返回字符数
    unsigned int numChar = countFrequency(infile,frequencies);

    if(0 == numChar){

        return 0;
    }
    // printFrequency(array); 对frequencies进行排序
    sortFrequency(frequencies);
    // 内容数组构建链表 频率从小到大
    ListNode * head = List_build(frequencies);
    if(NULL == head){
 
        return 0;
    }
    // 构成树 并返回根节点（将链表改建成树）
    ListNode * root = list2Tree(head);
    // 计算叶子节点
    int numRow = Tree_leaf(root);
    // 获得树的高度
    int numCol = Tree_height(root);
    // numCol应该加1来容纳最后的-1
    numCol++;

    int ** codebook = (int**)malloc(sizeof(int*) * numRow);
    int row;
    for(row = 0;row < numRow;row++){

        codebook[row] = malloc(sizeof(int) * numCol);
        int col;
        for(col = 0;col < numCol;col++){

            codebook[row][col] = -1;
        }
    }
    // 构建每个字符的编码方式
    buildCodeBook(root,codebook);
    // 输出树
    printCodeBook(codebook,numRow);

    // 字符映射
    int mapping[NUMLETTER];
    for(int index = 0;index < NUMLETTER;index++){

        mapping[index] = -1;
        int index2;
        for(index2 = 0;index2 < numRow;index2++){

            if(codebook[index2][0] == index){

                mapping[index] = index2;
            }
        }
    }
    // 输出字符映射表
    for(int index = 0;index < NUMLETTER;index++){

        if(mapping[index] != -1){

            printf("%c:%d\n",index,mapping[index]);
        }
    }
    // 头部
    Tree_header(root,numChar,outfile);
    // 内容
    compress(infile,outfile,codebook,mapping);
    // 释放内存
    for(int index = 0;index < numRow;index++){

        free(codebook[index]);
    }
    free(codebook);
    Tree_destroy(root);
    return 1;
}

static TreeNode * readHeader(FILE * infptr){

    int done = 0;
    unsigned char whichbit = 0;
    unsigned char curbit   = 0;
    unsigned char onebit   = 0;
    ListNode * head = NULL;

    while(done == 0){
        
        readBit(infptr,&onebit,&whichbit,&curbit);
        //
        if(onebit == 1){

            // 一个叶子节点 得到七个可位移的位
            int bitcount = 0;
            unsigned char value = 0;
            for(bitcount = 0;bitcount < 7;bitcount++){

                value = value << 1;
                // 读取这个字节后面的七位
                readBit(infptr,&onebit,&whichbit,&curbit);
                value = value | onebit;
            }
            // 构建树节点
            TreeNode * tn = TreeNode_create(value,0);
            // 构建链表节点
            ListNode * ln = ListNode_create(tn);
            // 插入到链表(非排序)
            head = List_insert(head,ln,STACK);
        }else{

            if(head == NULL){

                printf("ERROR, head should not be NULL.\n");
            }
            if(head->next == NULL){

                done = 1;
            }else{

                // 什么样的情况下会走到这一步？（就是在遇到命令位不是1的情况下）
                head = MergeListNode(head,DECODEMODE);
            }
        }
    }
    // 没有必要读取未用到的位
    TreeNode * root = head->tnptr;
    free(head);

    return root;
}

int decode(char * infile,char * outfile){

    // 打开要读取的文件
    FILE * infptr = fopen(infile,"r");
    if(NULL == infptr){

        return 0;
    }
    // 读取文件头部内容
    TreeNode * root = readHeader(infptr);
    // Tree_print(root,0);
    unsigned int numChar = 0;
    // 二进制读取(读取字符数量)
    fread(&numChar,sizeof(unsigned int),1,infptr);
    printf("numChar = %d.\n",numChar);
    // 读取换行符
    unsigned char newline;
    fread(&newline,sizeof(unsigned char),1,infptr);
    if(newline!='\n'){

        printf("ERROR!!.\n");
    }
    // 下面的就是读取内容
    unsigned char whichbit = 0;
    unsigned char onebit   = 0;
    unsigned char curbyte  = 0;
    FILE * outfptr = fopen(outfile,"w");
    while(numChar!=0){

        TreeNode * tn = root;
        // tn不是一个叶子节点
        while(tn->left!=NULL){

            readBit(infptr,&onebit,&whichbit,&curbyte);
            if(onebit == 0){

                tn = tn->left;
            }else{

                tn = tn->right;
            }
        }
        // tn是叶子节点（根据上面的遍历会遍历出第一个节点 即 第一个字符）
        printf("%c",tn->value);
        fprintf(outfile,"%c",tn->value);
        numChar--;
    }
    Tree_destroy(root);
    fclose(infptr);
    fclose(outfptr);

    return 1;
}

